1. Field of the Invention
This invention relates to an optimal solution search method and an optimal solution search apparatus as well as a storage medium in which an optimal solution search program is stored, suitable for use for optimization of a system using genetic algorithms (GAs), and contemplates provision of a technique for allowing genetic algorithms to be executed at a high speed to allow a high speed search for an optimal solution to a problem.
2. Description of the Related Art
In recent years, optimal solution search apparatus which search for an optimal solution to a problem using genetic algorithms have been conceived from a principle of biological evolution (selection (reproduction), mutation or crossover).
An optimal solution search apparatus which employs genetic algorithms, represents candidates for solution to a problem as chromosomes. Each chromosome is an arrangement of genes. The apparatus performs various genetic operations for the chromosomes to search for one of the optimal solutions each of which is obtained as one of the chromosomes having the highest fitness value.
It is to be noted that the fitness value is calculated from a gene arrangement of a chromosome and represents a degree of fitness to a problem. That is, a degree of quality of a solution represented by a chromosome.
An optimal solution search apparatus of the type mentioned above is typically constructed such that, at the end (or start) of a generation, a fitness value of a gene arrangement obtained as a result of the performance of genetic operations is calculated.
The optimal solution search apparatus has a problem in that, when genetic algorithms are executed, for calculation processing of fitness values is time consuming.
Particularly, when fitness values are calculated for gene arrangements obtained as a result of the performance of genetic operations (as in the optimal solution search apparatus described above)) a large amount of time is required for calculation processing of fitness values.
The optimal solution search apparatus has another problem in that, as the number of chromosomes which make an object of processing increases, or as the length of a chromosome which makes an object of processing increases, or as the calculation processing for fitness values becomes complicated, the time required for execution of genetic algorithms increases.
It is an object of the present invention to provide an optimal solution search method and apparatus wherein genetic algorithms can be executed at a high speed to allow an optimal solution to a problem to be searched for at a high speed.
It is another object of the present invention to provide a storage medium in which an improved optimal solution search program for operating a computer to search for an optimal solution is stored.
In order to attain the objects described above, according to an aspect of the present invention, there is provided an optimal solution search method wherein candidates for solution to a problem are represented as chromosomes, which are arrangements of genes and genetic operations, and are performed for individual chromosomes for each generation to successively update the generation to search for an optimal solution to the problem based on fitness values calculated from gene arrangements of the chromosomes, the optimal solution search method comprising the fitness value updating step of updating, for each of those chromosomes for which a particular genetic operation which allows a fitness value after execution thereof to be calculated readily making use of a fitness value before the execution thereof, and the fitness value based on variation information of the fitness value by execution of the particular genetic operation.
The optimal solution search method according to the present invention is advantageous in that, since the time required for calculation processing of fitness values can be reduced, genetic algorithms can be executed at a high speed and an optimal solution to a problem can be searched at a high speed.
According to another aspect of the present invention, there is provided an optimal solution search method wherein candidates for solution to a problem are represented as chromosomes, which are arrangements of genes and genetic operations, and are performed for individual chromosomes for each generation to successively update the generation to search for an optimal solution to the problem based on fitness values calculated from gene arrangements of the chromosomes, the optimal solution search method comprising the schedule determination step of determining, prior to execution of those genetic operations which remain before the end of a generation, an execution schedule of the genetic operations to be performed for each of the chromosomes, the chromosome discrimination step of referring to the execution schedules determined by the schedule determination step to discriminate, for each of the chromosomes, whether or not the chromosome is a particular chromosome for which only a particular genetic operation which allows a fitness value after execution thereof to be calculated readily making use of a fitness value before the execution thereof, and the fitness value updating step of updating, for each of those chromosomes which have been determined to be the particular chromosomes by the chromosome discrimination step, and the fitness value based on variation information of the fitness value by execution of the particular genetic operation.
In another aspect of the present invention, the fitness value updating step, the fitness values may be updated in synchronism with execution of the particular genetic operation.
In another aspect of the present invention, the fitness value updating step, upon execution of the particular genetic operation, variation information of the fitness value may be calculated by execution of the particular genetic operation.
In another aspect of the present invention, the fitness value updating step, upon execution of the particular genetic operation from among those genetic operations which make an object of determination in the schedule determination step, variation information of the fitness value may be calculated by execution of the particular genetic operation independently of a result of the discrimination in the chromosome discrimination step.
In another aspect of the present invention, in the fitness value updating step, variation information of the fitness value may be calculated by execution of the particular genetic operation after execution of an arbitrary one of those genetic operations which make an object of determination in the schedule determination step.
Upon execution of the particular genetic operation from among those genetic operations executed prior to one of the genetic operations which has been determined as an object of determination in the schedule determination step, variation information of the fitness value by execution of the particular genetic operation may be calculated.
In the schedule determination step, it is only required that the execution schedules be determined before the particular genetic operation appearing last is executed.
In another aspect of the present invention, in the schedule determination step, the execution schedules may be determined before the first genetic operation is executed, or before the particular genetic operation appearing first is executed, or before an arbitrary genetic operation is executed.
In another aspect of the present invention, in the schedule determination step, the execution schedules of genetic operations may be determined for the individual chromosomes, or an execution schedule of genetic operations which is common to all of the chromosomes may be determined.
In another aspect of the present invention, in the chromosome discrimination step, the execution schedules determined by the schedule determination step and also execution conditions of those genetic operations which have been executed prior to a genetic operation determined as an object of determination by the schedule determination step may be referred to to discriminate, for each of the chromosomes, whether or not the chromosome is a chromosome for which only the particular genetic operation should be performed.
In another aspect of the present invention, in the chromosome discrimination step, for each of the chromosomes, whether or not the chromosome is a chromosome for which the particular genetic operation should be performed may be discriminated before the particular genetic operation which appears last is executed.
In this instance, in the chromosome discrimination step, for each of the chromosomes, whether or not the chromosome is a chromosome for which the particular genetic operation should be performed may be discriminated before the first genetic operation is executed, or before the particular genetic operation which appears first is executed, or after an arbitrary genetic operation is executed.
In another aspect of the present invention, in the chromosome discrimination step, for each of the chromosomes, whether or not the chromosome is a chromosome for which only the particular genetic operation should be performed may be discriminated before the fitness value is updated by the fitness value updating step after the last genetic operation is executed.
With the optimal solution search method of the present invention, for each particular chromosome for which only the particular genetic operation which allows a fitness value after execution thereof to be calculated readily making use of a fitness value before the execution thereof, the fitness value is updated based on variation information of the fitness value by execution of the particular genetic operation. Consequently, the time required for calculation processing of fitness values can be reduced. Accordingly, the optimal solution search method is advantageous in that genetic algorithms can be executed at a high speed and an optimal solution to a problem can be searched at a high speed.
According to a further aspect of the present invention, there is provided an optimal solution search apparatus wherein candidates for solution to a problem are represented as chromosomes which are arrangements of genes and genetic operations are performed for individual chromosomes for each generation to successively update the generation to search for an optimal solution to the problem based on fitness values calculated from gene arrangements of the chromosomes, the optimal solution search apparatus comprising schedule determination means for determining, prior to execution of those genetic operations which remain before the end of a generation, an execution schedule of the genetic operations to be performed for each of the chromosomes, chromosome discrimination means for referring to the execution schedules determined by the schedule determination means to discriminate, for each of the chromosomes, whether or not the chromosome is a particular chromosome for which only a particular genetic operation which allows a fitness value after execution thereof to be calculated readily making use of a fitness value before the execution thereof, and fitness value updating means for updating, for each of those chromosomes which have been determined to be the particular chromosomes by the chromosome discrimination means, the fitness value based on variation information of the fitness value by execution of the particular genetic operation.
The schedule determination means may include a table for storing the execution schedules.
The chromosome discrimination means may include a table for storing information representing whether or not genetic operations to be performed for the individual chromosomes are the particular genetic operation, and another table for storing information representing whether or not the individual chromosomes are chromosomes for which only the particular genetic operation should be performed.
The optimal solution search apparatus of the present invention may further comprise updating pre-processing means for calculating, when the particular genetic operation from among those genetic operations executed prior to a genetic operation determined as an object of determination by the schedule determination means, variation information of the fitness value by execution of the particular genetic operation.
In another aspect of the present invention, the optimal solution search apparatus of the present invention may further comprise fitness value calculation means for calculating, for each of those chromosomes which have not been discriminated to be the particular chromosome by the chromosome discrimination means, a fitness value from a gene arrangement of the chromosome.
In another aspect of the present invention, the optimal solution search apparatus of the present invention may further comprise genetic operation execution means for performing the genetic operations for the individual chromosomes.
In another aspect of the present invention, the optimal solution search apparatus of the present invention may further comprise optimal solution discrimination means for discriminating an optimal solution to the problem based on the fitness value obtained by the fitness value updating means and the fitness value calculation means.
In another aspect of the present invention, the optimal solution search apparatus of the present invention may further comprise chromosome production means for representing candidates for solution to the problem as chromosomes which are arrangements of genes.
With the optimal solution search apparatus of the present invention, for each particular chromosome for which only the particular genetic operation which allows a fitness value after execution thereof to be calculated readily making use of a fitness value before the execution thereof, the fitness value is updated based on variation information of the fitness value by execution of the particular genetic operation. Consequently, the time required for calculation processing of fitness values can be reduced. Accordingly, the optimal solution search apparatus is advantageous in that genetic algorithms can be executed at a high speed and an optimal solution to a problem can be searched at a high speed.
According to a still further aspect of the present invention, there is provided a storage medium which stores an optimal solution search program for causing a computer to operate so that candidates for solution to a problem are represented as chromosomes which are arrangements of genes and genetic operations are performed for individual chromosomes for each generation to successively update the generation to search for an optimal solution to the problem based on fitness values calculated from gene arrangements of the chromosomes, wherein the optimal solution search program causes the computer to function as schedule determination means for determining, prior to execution of those genetic operations which remain before the end of a generation, an execution schedule of the genetic operations to be performed for each of the chromosomes, chromosome discrimination means for referring to the execution schedules determined by the schedule determination means to discriminate, for each of the chromosomes, whether or not the chromosome is a particular chromosome for which only a particular genetic operation which allows a fitness value after execution thereof to be calculated readily making use of a fitness value before the execution thereof, and fitness value updating means for updating, for each of those chromosomes which have been determined to be the particular chromosomes by the chromosome discrimination means, the fitness value based on variation information of the fitness value by execution of the particular genetic operation.
With the storage medium which stores the optimal solution search program of the present invention, for each particular chromosome for which the particular genetic operation which allows a fitness value after execution thereof to be calculated readily making use of a fitness value before the execution thereof, the fitness value is updated based on variation information of the fitness value by execution of the particular genetic operation. Consequently, the time required for calculation processing of fitness values can be reduced. Accordingly, the storage medium which stores the optimal solution search program is advantageous in that genetic algorithms can be executed at a high speed and an optimal solution to a problem can be searched at a high speed.